[BAEKJOON] 13308. 주유소

Posted on December 15, 2020

문제 :

어떤 나라에는 N개의 도시가 있고, 각 도시는 1번부터 N번까지 번호가 붙어 있다. 또, 서로 다른 두 도시를 양방향으로 직접 연결하는 M개의 도로가 있다. 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

1번 도시에서 N번 도시로 자동차를 이용하여 이동하려고 한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시와 4개의 도로가 있다고 하자. 원 안에 있는 숫자는 도시의 번호, 원 옆에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 옆에 있는 숫자는 도로의 길이를 표시한 것이다.

]

1번 도시에서 출발할 때 7리터의 기름을 넣고 그 기름으로 4번 도시까지 (3번 도시를 거쳐) 이동하면 총 비용은 35원이다. 만약 1번 도시에서 출발할 때 3리터의 기름을 넣고(3×5 = 15원) 3번 도시로 이동한 다음, 다시 3번 도시에서 4리터의 기름을 넣고(4×4 = 16원) 4번 도시에 도착하면 총 비용은 31원이다. 또 다른 방법으로 1번 도시에서 2리터의 기름을 넣고(2×5 = 10원) 2번 도시로 이동하여, 2번 도시에서 9리터의 기름을 넣고(9×2 = 18원) 1번과 3번 도시를 거쳐 4번 도시에 도착하면 총 비용은 28원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도로들의 길이를 입력으로 받아 1번 도시에서 N번 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력 :

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 수와 도로의 수를 나타내는 정수 N(2 ≤ N ≤ 2,500)과 정수 M(1 ≤ M ≤ 4,000)이 주어진다. 다음 줄에 각 도시 주유소의 리터당 가격이 도시 번호 순서대로 N개의 자연수로 주어진다. 리터당 가격은 1 이상 2,500 이하의 자연수이다. 그 다음 M개의 줄 각각에 하나의 도로에 대한 정보가 세 개의 자연수로 주어지는데, 처음 두 개의 자연수는 도로가 연결하는 두 도시의 번호이며, 세 번째 자연수는 도로의 길이이다. 도로의 길이는 1 이상 2,500 이하의 자연수이다. 한 쌍의 도시를 연결하는 도로는 최대 하나만 존재한다. 임의의 도시에서 다른 임의의 도시로 도로들을 이용하여 이동할 수 있는 방법이 항상 존재한다.

출력 :

표준 출력으로 1번 도시에서 N번 도시로 가는 최소 비용을 출력한다.

풀이 :

최근 시험기간이 끝난 후 그래프 문제들을 풀고 있는데 확실히 최근 푼 문제 중 가장 난이도가 높은 문제였다. 우선 시행착오와 해결 방법들을 중심으로 풀이를 적어보았다.

우선 처음에는 단순히 dfs 방식으로 주유 가격이 가장 낮은 경로를 구하는 방법을 구하려고 했다. → 하지만 본 문제는 방문한 주유소를 한 번 더 방문해도 무관한 경로도 포함되는 문제라서 단순히 경로탐색을 해서는 정답을 찾을 수 없었다.
그래서 현재 위치(주유소), 현재 최소 리터당 가격(minprice), 현재 주유 가격 합(sum)의 정보를 포함하는 구조체 Node로 구성되는 우선순위큐를 활용하여 bfs 방식으로 경로를 탐색해보았다. → 재방문 여부를 따지지 않고 주유 가격이 낮은 순으로 꺼낼 수 있는 우선순위 큐를 구현하였음.
예제 테스트 케이스의 경우는 통과할 수 있었으나 주요소 갯수가 최대로 늘어나게 되면 바로 메모리 초과가 일어났다. → 재방문 여부를 효과적으로 확인하지 않아서 큐에 너무 많은 노드가 채워지게 되는 문제가 발생하는 것.
이 문제를 해결하기 위해 dp방식을 활용하여야 했다. 처음 dp 방식은 행을 현재 주유소 위치, 열을 현재 최소 리터당 가격을 의미하는 2차원 배열로 만들어 값은 현재 주유 가격합을 담고 있도록 구현하였다. 이 방식은 방문했던 주유소를 재 방문했을 때 전에 방문했던 경우와 최소 리터당 가격이 같은데 현재 주유 가격합은 전보다 더 높을 경우에는 큐에 담지 않도록 구현하였다. → 이방법은 이상하게 계속 시간초과가 났다.. 아마도 방문할 때 마다 비교 연산과정이 하나가 늘어난 탓이 아닐까 싶어 다른 방식으로 dp를 구현해보았다.
이번에는 dp 배열을 단순히 방문여부만을 따지는 true/false 배열로 구현했다. 행과 열의 의미는 동일하게 두고 우선순위큐에서 작은 값부터 꺼내기 때문에 나중에 방문하는 경우는 항상 주유 가격 합이 클 것이기 때문에 굳이 연산 과정을 거칠 필요가 없다고 생각했다. → 본 방법을 통해 시간초과 문제를 해결할 수 있었다.

그래프 문제들은 확실히 조금만 더 어려워지더라도 많은 시간이 소요되는 것 같다. 우선 대충 접근 방법을 떠올려보더라도 구현 자체도 꽤나 까다로운 문제들이 많기 때문에 더 꾸준히 부지런히 풀어볼 필요가 있는 것 같다.

코드 :

코드 보기/접기

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>

#define MAX 15626000000
#define pii pair<int, int>

using namespace std;
typedef struct Node {
    long sum;
    int minprice;
    int cur;
} Node;

struct cmp {
    bool operator()(Node t, Node u) {
        return t.sum > u.sum;
    }
};

int *prices, n;
long answer = MAX;
bool dp[2501][2501];
vector<vector<pii>> route;

void bfs(int cur, int minprice, long sum) {
    priority_queue<Node, vector<Node>, cmp> pq;
    pq.push(Node{sum, minprice, cur});
    int size, i, next, nextprice;
    long nextsum;
    while (!pq.empty()) {
        cur = pq.top().cur;
        minprice = pq.top().minprice;
        sum = pq.top().sum;
        pq.pop();

        if (sum >= answer) break;
        if (dp[cur][minprice]) continue;

        dp[cur][minprice] = true;
        size = route[cur].size();
        for (i = 0; i < size; i++) {
            next = route[cur][i].first;
            nextsum = sum + minprice * route[cur][i].second;
            nextprice = min(minprice, prices[next]);
            if (nextsum > answer) continue;
            if (next == n) {
                answer = min(answer, nextsum);
                continue;
            }
            pq.push(Node{nextsum, nextprice, next});
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int m, i, fir, sec, dist;
    cin >> n >> m;
    prices = new int[n + 1]{0};
    for (i = 1; i <= n; i++)
        cin >> prices[i];
    route.resize(n + 1);
    while (m--) {
        cin >> fir >> sec >> dist;
        route[fir].push_back(pii(sec, dist));
        route[sec].push_back(pii(fir, dist));
    }

    bfs(1, prices[1], 0);
    cout << answer << '\n';

    return 0;
}

Algorithm

algorithm baekjoon C++